package red.book._1._1;

/**
 * 素数作为数据界中耀眼的一环， 有很多人再不断研究， 著名的有黎曼猜想。
 * 
 * 通过平凡根的方式优化判断一个数是否为素数。
 * 继续优化， 使用6倍法在上面的基础继续判断一个数是否为素数。
 * TODO 埃拉托斯特尼算法来进行素数的筛选
 * TODO 米勒罗宾素性测试
 * @author wangbingwu
 *
 */
public class IsPrimeNumberBySquareRootMethod {
	public static void main(String[] args) {
		int num = 30;
		
		System.out.println("The number " + num);
		System.out.println("Optimize the judgment of whether it is a prime number by square root ? " + 
				isPrimeNumberBetterModeBySquareRoot(num));

		System.out.println("Optimize the judgment of whether it is a prime number by 6 times method ? " + 
				isPrimeNumberBetterModeBy6TimesMethod(num));
	}

	private static boolean isPrimeNumberBetterModeBy6TimesMethod(int num) {
		if(num < 2) {
			return false;
		}else if(num < 4) {
			return true;
		}
		
		if(num % 6 != 1 && num % 6 != 5) {
			return false;
		}
		
		for(int i = 5; i * i <= num; i =+ 6) {
			if(num % i == 0 || num % (i + 2) == 0) {
				return false;
			}
		}
		
		return true;
	}

	private static boolean isPrimeNumberBetterModeBySquareRoot(int num) {
		if(num < 2) {
			return true;
		}
		
		for(int i = 2; i * i <= num; i++) {
			if(num % i == 0) {
				return false;
			}
		}
		return true;
	}
}
